import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86183
 * Date: 2022-10-24
 * Time: 9:45
 */

public class Test {
    /**
     * 归并排序
     * 时间复杂度：O(n*logn)
     * 空间复杂度 O(n)
     * 稳定性：稳定
     * @param array
     */
    public static void merger(int[] array){

        mergerChild(array,0,array.length-1);
    }

    private static void mergerChild(int[] array, int left, int right) {
        if(left == right){
            return;
        }
        int mid = (left+right)/2;
        mergerChild(array,left,mid);
        mergerChild(array,mid+1,right);
        merge(array,left,mid,right);
    }

    private static void merge(int[] array, int left, int mid, int right) {
         int s1 = left;
         int e1 = mid;
         int s2 = mid+1;
         int e2 = right;
         int k = 0;
         int[] tmp = new int[right - left+1];
         while (s1 <= e1&& s2 <= e2){
             if(array[s1] < array[s2]){
                 tmp[k++] = array[s1++];
             }else {
                 tmp[k++] = array[s2++];
             }
         }
         while (s1 <= e1){
             tmp[k++]= array[s1++];
         }
        while (s2 <= e2){
            tmp[k++]= array[s2++];
        }
        for (int i = 0; i < k; i++) {
            array[i+left] = tmp[i];
        }
    }
    public static void mergerSort(int[] array){
        int gap = 1;
        while (gap < array.length){
            for (int i = 0; i < array.length; i+= gap*2) {
                int left = i;
                int mid = left + gap -1;
                int right = mid + gap;
                if(mid >= array.length){
                    mid = array.length -1;
                }
                if(right >= array.length){
                    right = array.length -1;
                }
                merge(array,left,mid,right);
            }
            gap *= 2;
        }
    }

    public static void main(String[] args) {
        int[] array ={99,45,67,23,46,89,12,3};
        merger(array);
        System.out.println(Arrays.toString(array));
    }
}
